home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 185_01 / bosesort.mss < prev    next >
Text File  |  1985-08-19  |  2KB  |  47 lines
  1.  
  2.  
  3. @closing(5-SEP-85)
  4.  
  5.  
  6. This document outlines the usage of my version of the Bose-Nelson
  7. sorting algorithm presented in the September 1985 issue of Dr.
  8. Dobbs.  As far as I could tell, both programs that were presented
  9. (in good faith I presume), were not functional as written. 
  10. Rather than try to correct the bugs, I wrote my own version of
  11. the recursive program.
  12.  
  13. The version of "BOSE.COM" that is contained in this library will
  14. run on Z80 CP/M only.  You will have to recompile "BOSE.C" to
  15. suit your machine and C compiler, if this is not the case.
  16.  
  17. The "BOSE.COM" program will generate a program containing the
  18. swap pairs for a known, fixed set of elements.  To use the
  19. program, type "BOSE <#> <filespec.ext>", where "#" is the number
  20. of elements to be sorted and "filespec.ext" is any legal file
  21. name that you wish.  I use ".c" as my extension.
  22.  
  23. A few notes about the efficientcy of both the speed of
  24. generating the swap pairs and the object code size.  The
  25. Bose-Nelson algorithm begins to take excessive amouts of time
  26. when the number of elements gets above 200-300.  For this many
  27. elements, there are about 12,000 ( right! 12K) swaps.  Thats
  28. about 20k in swap code alone for my rather inefficient (remaining
  29. nameless) C compiler.  However, the speed is quite excellent. 
  30. For the example ("STEST.C") sort of 50 random integers, it puts
  31. quicksort to shame.  Try it!
  32.  
  33. Anyway, enjoy the program.  I'm sure that you will be pleased to
  34. have a working version of the algorithm.  Several improvements
  35. are in order, but the first that comes to mind is to reduce that
  36. number of swaps involved for large amounts of elements.  It was
  37. mentioned in Dr. D's that this routine did not generate optimal
  38. sorts.  They weren't kidding.
  39.  
  40. @closing(Mark D. Lougheed
  41. 6704 Sierra Drive S.E.
  42. Lacey Wa
  43. 98503)
  44. legal file
  45. name that you wish.  I use ".c" as my extension.
  46.  
  47. A few notes about the ef